# 字符串编辑距离

import os
import numpy as np

def damerau_levenshtein_distance(string1, string2,len1 = 5,diff_dir = "./",print_log = True):
    # string1  预测值
    # string2  标签值
    # len1 是log中打印的长度
    # diff_dir 是分析结果保存的目录
    string1 = string1.strip("\n")
    string2 = string2.strip("\n")
    # 藏语有两种格式的点，这里只考虑一种
    string1 = string1.replace('༌', '་')
    string2 = string2.replace('༌', '་')
    # 标签会带一些特殊符号
    string2 = string2.replace(' ', ' ')
    string2 = string2.replace('​', '')
    # 忽略空格
    string2 = string2.replace(' ', '')
    string1 = string1.replace(' ', '')
    # 缅甸语可以先写上面的勾再写圈，也可以反过来，最终都是一样的效果
    string1 = string1.replace('့်', '့်')
    string2 = string2.replace('့်', '့်')
    m = len(string1)
    n = len(string2)
    d = [[0] * (n + 1) for _ in range(m + 1)]
    # 初始化第 1 列  一个空字符到其他字符的操作数
    for i in range(m + 1):
        d[i][0] = i
    # 初始化第 1 行  一个空字符到其他字符的操作数
    for j in range(n + 1):
        d[0][j] = j
    # 自底向上递推计算每个 d[i][j] 的值
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if string1[i - 1] == string2[j - 1]:
                d[i][j] = d[i - 1][j - 1]
            else:
                d[i][j] = min(d[i - 1][j], d[i][j - 1], d[i - 1][j - 1]) + 1


    ddd = d[m][n]
    if not print_log:
        return ddd
    # 得到编辑距离，下面开始分析
    fw = open(os.path.join(diff_dir,"diff.txt"), 'a', encoding="utf-8")  # 将要输出保存的文件地址
    if ddd != 0:
        if m * n == 0:
            fw.write("edit distant: " + str(ddd) + "\n")
            fw.close()
            return ddd
        i = m
        j = n
        log = []
        dist_trace_complit = []
        dist_trace_complit.append([m, n])
        # 从下往上计算
        while i > 0 or j > 0:
            # 如果不在最左或最上，那么有三个方向
            if i * j > 0 :
                # 在三个方向种，哪个方向上的d是最小的 上，左，左上
                index_temp = np.argmin([d[i - 1][j], d[i][j - 1]])
                if d[i - 1][j - 1] <= min(d[i - 1][j], d[i][j - 1]):
                    index_temp = 2
                # 下一步的位置记为为trace1 更新trace1
                trace1 = []
                if index_temp == 0:
                    trace1 = [i - 1, j]
                elif index_temp == 1:
                    trace1 = [i, j - 1]
                elif index_temp == 2:
                    trace1 = [i - 1, j - 1]
            # 如果已经在最左或最上，那么就少了两个方向
            else:
                if i == 0:
                    index_temp = 1
                    trace1 = [i, j - 1]
                else:
                    index_temp = 0
                    trace1 = [i - 1, j]
            # 当前这个位置的对应的dis 和下一步位置的dis进行比较
            # 如果不相等说明进行了编辑操作
            if d[i][j] != d[trace1[0]][trace1[1]]:
                blank = ""

                # left right 是拿到当前字符前len1个字符，目的是为了日志可读性
                left = i - 1 - len1
                left = max(left, 0)
                rignt = i - 1 + len1
                rignt = min(rignt, m)

                left2 = j - 1 - len1
                left2 = max(left2, 0)
                rignt2 = j - 1 + len1
                rignt2 = min(rignt2, n)
                # push log信息
                if index_temp == 0:
                    log.append(blank + "\t#  " + string1[max(i-1,0)] + "  # need del" + "\n")
                    log.append(blank + "pre1:  " + string1[left:rignt: 1] + "\ngdt1:  " + string2[left2:rignt2: 1] + "\n")
                if index_temp == 1:
                    log.append(blank + "\t#  " + string1[max(i-1,0)] + "  # need insert #  " + string2[max(j-1,0)] + "  #\n")
                    log.append(blank + "pre1:  " + string1[left:rignt: 1] + "\ngdt1:  " + string2[left2:rignt2: 1] + "\n")
                if index_temp == 2:
                    log.append(blank + "\t#  " + string1[max(i-1,0)] + "# need replace #  " + string2[max(j-1,0)] + "  #\n")
                    log.append(blank + "pre1:  " + string1[left:rignt: 1] + "\ngdt1:  " + string2[left2:rignt2: 1] + "\n")

            dist_trace_complit.append(trace1)
            i = trace1[0]
            j = trace1[1]
        fw.write("gt total len: " + str(n) + "\n")
        fw.write("edit distant: " + str(ddd) + "\n")  # 将字符串写入文件中

        for i in range(len(log)):
            fw.write(log.pop())
        fw.write("\n")
        fw.write("\n")


    fw.close()
    return ddd

# 这个函数没卵用 这是只考虑插入和替换操作没有删除操作
def damerau_levenshtein_distance_no_del(string1, string2):
    return 0
    m = len(string1)
    n = len(string2)
    # n+1行 m+1列  表示由 m 对应的字符串转到 n 对应的字符串
    d = [[0] * (n + 1) for _ in range(m + 1)]

    # 初始化第 1 行  一个空字符到其他字符的操作数
    for j in range(n + 1):
        d[0][j] = j
    # 初始化第 1 列  一个空字符到其他字符的操作数
    d[1][0] = 1
    for i in range(2, m + 1):
        d[i][0] = min(i, d[i - 1][0])
    # 自底向上递推计算每个 d[i][j] 的值
    # 一行行填充值
    for i in range(1, m + 1):
        # string11 = string1[0:i]
        for j in range(1, n + 1):
            # string22 = string2[0:j]
            if string1[i - 1] == string2[j - 1]:
                d[i][j] = d[i - 1][j - 1]
                # pass
            else:
                import numpy as np
                d[i][j] = min(d[i - 1][j], d[i][j - 1], d[i - 1][j - 1]) + min(
                    np.argmin([d[i - 1][j], d[i][j - 1], d[i - 1][j - 1]]), 1)

                # pass
            # if i > 1 and j > 1 and string1[i - 1] == string2[j - 2] and string1[i - 2] == string2[j - 1]:
            #     d[i][j] = min(d[i][j], d[i - 2][j - 2] + 1)
    return d[m][n]






